package tree;

import java.util.LinkedList;
import java.util.Queue;

public class BinarySearchTree {

    private class Node{
        public int value;
        public Node left;
        public Node right;


        public Node(int value){
            this.value = value;
            left = null;
            right = null;
        }
    }

    private Node root;
    private int size;



    public int getSize(){
        return size;
    }

    public boolean isEmpty(){
        return size==0;
    }

    //二分搜索树添加元素
    public void add(int value){
         root = add(root,value);
    }

    //返回新二分搜索树的根节点
    private Node add(Node node,int value){

        if(node == null){
            size++;
            return new Node(value);
        }

        if(value < node.value){
            //安排在左子树上
            node.left = add(node.left,value);
        }else if(value > node.value){
            node.right = add(node.right,value);
        }

        return node;


    }

    //前序遍历
    public void preOrder(){
        preOrder(root);
    }

    private void preOrder(Node node){
        if(node == null){
            return ;
        }
        System.out.println("前序遍历：" + node.value);
        preOrder(node.left);
        preOrder(node.right);
    }

    //中序遍历
    private void inOrder(Node node){
        if(node == null){
            return;
        }

        inOrder(node.left);
        System.out.println("中序遍历：" + node.value);
        inOrder(node.right);
    }

    //后序遍历
    private void postOrder(Node node){
        if(node == null){
            return;
        }

        postOrder(node.left);
        postOrder(node.right);
        System.out.println("后序遍历：" + node.value);
    }

    //层序遍历——广度优先遍历
    private void levelOrder(){
        //使用队列，先进先出
        LinkedList<Node> q = new LinkedList();
        q.add(root);

        while (!q.isEmpty()){
            Node cur = q.remove();
            System.out.println(cur.value);

            if(cur.left != null){
                q.add(cur.left);
            }

            if(cur.right != null){
                q.add(cur.right);
            }
        }

    }

    public int minimum(){
        if(root == null){
            //提示用户错误
        }
        return minimum(root).value;
    }

    //获取二分搜索中最小的值
    private Node minimum(Node node){
        if(node.left == null){
            return node;
        }

        return minimum(node.left);
    }

    //删除二分搜索树中的最小值和最大值
    public int removeMin(){
        int ret = minimum();
        //删除二分搜索树中最小的值的节点
        root = removeMin(root);
        return ret;

    }


    //删除以Node为跟的二分搜索树最小节点
    //返回删除节点后的新二分搜索树的根
    private Node removeMin(Node node){
        if(node.left == null){
            Node rightNode = node.right;
            node.right = null;
            size--;
            return rightNode;
        }

        node.left = removeMin(node.left);
        return node;

    }


    /**
     *         4                                          4
             /   \             反转后                   /    \
            2     7        — — — — — — — — — —>       7      2
           / \   / \                                 /  \   / \
          1   3 6   9                               9   6  3   1
     *
     *
     *
     * @param node
     */
    public Node invert(Node node){

        if(node == null){
          return null;
        }

        //就是遍历
        if(node.left != null){
            invert(node.left);
        }
        if(node.right != null){
            invert(node.right);
        }

        Node temp = node.left;
        node.left = node.right;
        node.right = temp;
        return node;
    }





}
